Logic And Set Theory

• 1.II.16F

  Logic and Set Theory

  Part II, 2005

  State and prove Zorn's Lemma. [You may assume Hartogs' Lemma.] Where in your argument have you made use of the Axiom of Choice?

  Show that $\mathbb{R}$, considered as a rational vector space, has a basis.

  Prove that $\mathbb{R}$ and $\mathbb{R}^{2}$ are isomorphic as rational vector spaces.

  comment

• 2.II.16F

  Logic and Set Theory

  Part II, 2005

  Give the inductive and the synthetic definitions of ordinal addition, and prove that they are equivalent. Give an example to show that ordinal addition is not commutative.

  Which of the following assertions about ordinals $\alpha, \beta$ and $\gamma$ are always true, and which can be false? Give proofs or counterexamples as appropriate.

  (i) $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$.

  (ii) If $\alpha$ and $\beta$ are limit ordinals then $\alpha+\beta=\beta+\alpha$.

  (iii) If $\alpha+\beta=\omega_{1}$ then $\alpha=0$ or $\alpha=\omega_{1}$.

  (iv) If $\alpha+\beta=\omega_{1}$ then $\beta=0$ or $\beta=\omega_{1}$.

  comment

• 3.II.16F

  Logic and Set Theory

  Part II, 2005

  State the Axiom of Foundation and the Principle of $\in$-Induction, and show that they are equivalent (in the presence of the other axioms of ZF). [You may assume the existence of transitive closures.]

  Explain briefly how the Principle of $\in$-Induction implies that every set is a member of some $V_{\alpha}$.

  For each natural number $n$, find the cardinality of $V_{n}$. For which ordinals $\alpha$ is the cardinality of $V_{\alpha}$ equal to that of the reals?

  comment

• 4.II.16F

  Logic and Set Theory

  Part II, 2005

  State and prove the Completeness Theorem for Propositional Logic. [You do not need to give definitions of the various terms involved. You may assume that the set of primitive propositions is countable. You may also assume the Deduction Theorem, provided that you state it clearly.]

  Where in your argument have you used the third axiom, namely $(\neg \neg p) \Rightarrow p ?$

  State the Compactness Theorem, and deduce it from the Completeness Theorem.

  comment

• 1.II.16H

  Logic and Set Theory

  Part II, 2006

  Explain what it means for a poset to be chain-complete. State Zorn's Lemma, and use it to prove that, for any two elements $a$ and $b$ of a distributive lattice $L$ with $b \not{\leftarrow} a$, there exists a lattice homomorphism $f: L \rightarrow\{0,1\}$ with $f(a)=0$ and $f(b)=1$. Explain briefly how this result implies the completeness theorem for propositional logic.

  comment

• 2.II.16H

  Logic and Set Theory

  Part II, 2006

  Which of the following statements are true, and which false? Justify your answers.

  (a) For any ordinals $\alpha$ and $\beta$ with $\beta \neq 0$, there exist ordinals $\gamma$ and $\delta$ with $\delta<\beta$ such that $\alpha=\beta . \gamma+\delta$.

  (b) For any ordinals $\alpha$ and $\beta$ with $\beta \neq 0$, there exist ordinals $\gamma$ and $\delta$ with $\delta<\beta$ such that $\alpha=\gamma \cdot \beta+\delta$.

  (c) $\alpha \cdot(\beta+\gamma)=\alpha \cdot \beta+\alpha \cdot \gamma$ for all $\alpha, \beta, \gamma$.

  (d) $(\alpha+\beta) \cdot \gamma=\alpha \cdot \gamma+\beta \cdot \gamma$ for all $\alpha, \beta, \gamma$.

  (e) Any ordinal of the form $\omega . \alpha$ is a limit ordinal.

  (f) Any limit ordinal is of the form $\omega . \alpha$.

  comment

• 3.II.16H

  Logic and Set Theory

  Part II, 2006

  Explain what is meant by a structure for a first-order signature $\Sigma$, and describe how first-order formulae over $\Sigma$ are interpreted in a given structure. Show that if $B$ is a substructure of $A$, and $\phi$ is a quantifier-free formula (with $n$ free variables), then

  $$\llbracket \phi \rrbracket_{B}=\llbracket \phi \rrbracket_{A} \cap B^{n}$$

  A first-order theory is said to be inductive if its axioms all have the form

  $$\left(\forall x_{1}, \ldots, x_{n}\right)\left(\exists y_{1}, \ldots, y_{m}\right) \phi$$

  where $\phi$ is quantifier-free (and either of the strings $x_{1}, \ldots, x_{n}$ or $y_{1}, \ldots, y_{m}$ may be empty). If $T$ is an inductive theory, and $A$ is a structure for the appropriate signature, show that the poset of those substructures of $A$ which are $T$-models is chain-complete.

  Which of the following can be expressed as inductive theories over the signature with one binary predicate symbol $\leqslant$ ? Justify your answers.

  (a) The theory of totally ordered sets without greatest or least elements.

  (b) The theory of totally ordered sets with greatest and least elements.

  comment

• 4.II.16H

  Logic and Set Theory

  Part II, 2006

  Explain carefully what is meant by a well-founded relation on a set. State the recursion theorem, and use it to prove that a binary relation $r$ on a set $a$ is well-founded if and only if there exists a function $f$ from $a$ to some ordinal $\alpha$ such that $(x, y) \in r$ implies $f(x)<f(y)$.

  Deduce, using the axiom of choice, that any well-founded relation on a set may be extended to a well-ordering.

  comment

• 1.II.16G

  Logic and Set Theory

  Part II, 2008

  What is a well-ordered set? Show that given any two well-ordered sets there is a unique order isomorphism between one and an initial segment of the other.

  Show that for any ordinal $\alpha$ and for any non-zero ordinal $\beta$ there are unique ordinals $\gamma$ and $\delta$ with $\alpha=\beta \cdot \gamma+\delta$ and $\delta<\beta$.

  Show that a non-zero ordinal $\lambda$ is a limit ordinal if and only if $\lambda=\omega \cdot \gamma$ for some non-zero ordinal $\gamma$.

  [You may assume standard properties of ordinal addition, multiplication and subtraction.]

  comment

• 2.II.16G

  Logic and Set Theory

  Part II, 2008

  (i) State the Completeness Theorem and the Compactness Theorem for the predicate calculus.

  (ii) Show that if a theory has arbitrarily large finite models then it has an infinite model. Deduce that there is no first order theory whose models are just the finite fields of characteristic 2 . Show that the theory of infinite fields of characteristic 2 does not have a finite axiomatisation.

  (iii) Let $\mathcal{T}$ be the collection of closed terms in some first order language $\mathcal{L}$. Suppose that $\exists x . \phi(x)$ is a provable sentence of $\mathcal{L}$ with $\phi$ quantifier-free. Show that the set of sentences $\{\neg \phi(t): t \in \mathcal{T}\}$ is inconsistent.

  [Hint: consider the minimal substructure of a model.]

  Deduce that there are $t_{1}, t_{2}, \ldots, t_{n}$ in $\mathcal{T}$ such that $\phi\left(t_{1}\right) \vee \phi\left(t_{2}\right) \vee \cdots \vee \phi\left(t_{n}\right)$ is provable.

  comment

• 3.II.16G

  Logic and Set Theory

  Part II, 2008

  What is a transitive set? Show that if $x$ is transitive then so are the union $\bigcup x$ and the power set $P x$ of $x$. If $\bigcup x$ is transitive, is $x$ transitive? If $P x$ is transitive, is $x$ transitive? Justify your answers.

  What is the transitive closure of a set? Show that any set $x$ has a transitive closure $T C(x)$.

  Suppose that $x$ has rank $\alpha$. What is the rank of $P x$ ? What is the rank of $T C(x)$ ?

  [You may use standard properties of rank.]

  comment

• 4.II.16G

  Logic and Set Theory

  Part II, 2008

  Prove Hartog's Lemma that for any set $x$ there is an ordinal $\alpha$ which cannot be mapped injectively into $x$.

  Now assume the Axiom of Choice. Prove Zorn's Lemma and the Well-ordering Principle.

  [If you appeal to a fixed point theorem then you should state it clearly.]

  comment

• Paper 4, Section II, G

  Logic and Set Theory

  Part II, 2009

  What is a transitive class? What is the significance of this notion for models of set theory?

  Prove that for any set $x$ there is a least transitive set $\mathrm{TC}(x)$, the transitive closure of $x$, with $x \subseteq \mathrm{TC}(x)$. Show that for any set $x$, one has $\mathrm{TC}(x)=x \cup \mathrm{TC}(\bigcup x)$, and deduce that $\mathrm{TC}(\{x\})=\{x\} \cup \operatorname{TC}(x)$.

  A set $x$ is hereditarily countable when every member of $\mathrm{TC}(\{x\})$ is countable. Let $(\mathrm{HC}, \in)$ be the collection of hereditarily countable sets with the usual membership relation. Is HC transitive? Show that $(\mathrm{HC}, \in)$ satisfies the axiom of unions. Show that $(\mathrm{HC}, \in)$ satisfies the axiom of separation. What other axioms of ZF set theory are satisfied in $(\mathrm{HC}, \in) ?$

  comment

• Paper 3, Section II, G

  Logic and Set Theory

  Part II, 2009

  Let $x \subseteq \alpha$ be a subset of a (von Neumann) ordinal $\alpha$ taken with the induced ordering. Using the recursion theorem or otherwise show that $x$ is order isomorphic to a unique ordinal $\mu(x)$. Suppose that $x \subseteq y \subseteq \alpha$. Show that $\mu(x) \leqslant \mu(y) \leqslant \alpha$.

  Suppose that $x_{0} \subseteq x_{1} \subseteq x_{2} \subseteq \cdots$ is an increasing sequence of subsets of $\alpha$, with $x_{i}$ an initial segment of $x_{j}$ whenever $i<j$. Show that $\mu\left(\bigcup_{n} x_{n}\right)=\bigcup_{n} \mu\left(x_{n}\right)$. Does this result still hold if the condition on initial segments is omitted? Justify your answer.

  Suppose that $x_{0} \supseteq x_{1} \supseteq x_{2} \supseteq \cdots$ is a decreasing sequence of subsets of $\alpha$. Why is the sequence $\mu\left(x_{n}\right)$ eventually constant? Is it the case that $\mu\left(\bigcap_{n} x_{n}\right)=\bigcap_{n} \mu\left(x_{n}\right)$ ? Justify your answer.

  comment

• Paper 1, Section II, G

  Logic and Set Theory

  Part II, 2009

  Prove that if $G:$ On $\times V \rightarrow V$ is a definable function, then there is a definable function $F:$ On $\rightarrow V$ satisfying

  $$F(\alpha)=G(\alpha,\{F(\beta): \beta<\alpha\})$$

  Define the notion of an initial ordinal, and explain its significance for cardinal arithmetic. State Hartogs' lemma. Using the recursion theorem define, giving justification, a function $\omega:$ On $\rightarrow$ On which enumerates the infinite initial ordinals.

  Is there an ordinal $\alpha$ with $\alpha=\omega_{\alpha} ?$ Justify your answer.

  comment

• Paper 2, Section II, G

  Logic and Set Theory

  Part II, 2009

  (i) Give an axiom system and rules of inference for the classical propositional calculus, and explain the notion of syntactic entailment. What does it mean to say that a set of propositions is consistent? Let $P$ be a set of primitive propositions and let $\Phi$ be a maximal consistent set of propositional formulae in the language based on $P$. Show that there is a valuation $v: P \rightarrow\{T, F\}$ with respect to which all members of $\Phi$ are true.

  [You should state clearly but need not prove those properties of syntactic entailment which you use.]

  (ii) Exhibit a theory $T$ which axiomatizes the collection of groups all of whose nonunit elements have infinite order. Is this theory finitely axiomatizable? Is the theory of groups all of whose elements are of finite order axiomatizable? Justify your answers.

  comment

• Paper 1, Section II, G

  Logic and Set Theory

  Part II, 2010

  Show that $\aleph_{\alpha}^{2}=\aleph_{\alpha}$ for all $\alpha$.

  An infinite cardinal $m$ is called regular if it cannot be written as a sum of fewer than $m$ cardinals each of which is smaller than $m$. Prove that $\aleph_{0}$ and $\aleph_{1}$ are regular.

  Is $\aleph_{2}$ regular? Is $\aleph_{\omega}$ regular? Justify your answers.

  comment

• Paper 2, Section II, G

  Logic and Set Theory

  Part II, 2010

  Let $\alpha$ be a non-zero ordinal. Prove that there exists a greatest ordinal $\beta$ such that $\omega^{\beta} \leqslant \alpha$. Explain why there exists an ordinal $\gamma$ with $\omega^{\beta}+\gamma=\alpha$. Prove that $\gamma$ is unique, and that $\gamma<\alpha$.

  A non-zero ordinal $\alpha$ is called decomposable if it can be written as the sum of two smaller non-zero ordinals. Deduce that if $\alpha$ is not a power of $\omega$ then $\alpha$ is decomposable.

  Conversely, prove that if $\alpha$ is a power of $\omega$ then $\alpha$ is not decomposable.

  [Hint: consider the cases $\alpha=\omega^{\beta}$ ( $\beta$ a successor) and $\alpha=\omega^{\beta}$ ( $\beta$ a limit) separately.]

  comment

• Paper 3, Section II, G

  Logic and Set Theory

  Part II, 2010

  Define the sets $V_{\alpha}, \alpha \in O N$. What is meant by the rank of a set?

  Explain briefly why, for every $\alpha$, there exists a set of rank $\alpha$.

  Let $x$ be a transitive set of rank $\alpha$. Show that $x$ has an element of rank $\beta$ for every $\beta<\alpha$.

  For which $\alpha$ does there exist a finite set of rank $\alpha$ ? For which $\alpha$ does there exist a finite transitive set of rank $\alpha$ ? Justify your answers.

  [Standard properties of rank may be assumed.]

  comment

• Paper 4, Section II, G

  Logic and Set Theory

  Part II, 2010

  State and prove the Completeness Theorem for Propositional Logic.

  [You do not need to give definitions of the various terms involved. You may assume that the set of primitive propositions is countable. You may also assume the Deduction Theorem.]

  Explain briefly how your proof should be modified if the set of primitive propositions is allowed to be uncountable.

  comment

• Paper 1, Section II, H

  Logic and Set Theory

  Part II, 2011

  Give the inductive and synthetic definitions of ordinal addition, and prove that they are equivalent.

  Which of the following assertions about ordinals $\alpha, \beta$ and $\gamma$ are always true, and which can be false? Give proofs or counterexamples as appropriate.

  (i) $\alpha \beta=\beta \alpha$.

  (ii) $\alpha(\beta+\gamma)=\alpha \beta+\alpha \gamma$.

  (iii) If $\alpha \geqslant \omega^{2}$ then $\alpha+\omega^{2}=\omega^{2}+\alpha$.

  (iv) If $\alpha \geqslant \omega_{1}$ then $\alpha \omega_{1}=\omega_{1} \alpha$.

  comment

• Paper 2, Section II, H

  Logic and Set Theory

  Part II, 2011

  State and prove Zorn's Lemma. [You may assume Hartogs' Lemma.] Where in your argument have you made use of the Axiom of Choice?

  Show that every real vector space has a basis.

  Let $V$ be a real vector space having a basis of cardinality $\aleph_{1}$. What is the cardinality of $V$ ? Justify your answer.

  comment

• Paper 3, Section II, H

  Logic and Set Theory

  Part II, 2011

  State and prove the Upward Löwenheim-Skolem Theorem.

  [You may assume the Compactness Theorem, provided that you state it clearly.]

  A total ordering $(X,<)$ is called dense if for any $x<y$ there exists $z$ with $x<z<y$. Show that a dense total ordering (on more than one point) cannot be a well-ordering.

  For each of the following theories, either give axioms, in the language of posets, for the theory or prove carefully that the theory is not axiomatisable in the language of posets.

  (i) The theory of dense total orderings.

  (ii) The theory of countable dense total orderings.

  (iii) The theory of uncountable dense total orderings.

  (iv) The theory of well-orderings.

  comment

• Paper 4, Section II, H

  Logic and Set Theory

  Part II, 2011

  Define the sets $V_{\alpha}$ for ordinals $\alpha$. Show that each $V_{\alpha}$ is transitive. Show also that $V_{\alpha} \subseteq V_{\beta}$ whenever $\alpha \leqslant \beta$. Prove that every set $x$ is a member of some $V_{\alpha}$.

  For which ordinals $\alpha$ does there exist a set $x$ such that the power-set of $x$ has rank $\alpha$ ? [You may assume standard properties of rank.]

  comment

• Paper 2, Section II, H

  Logic and Set Theory

  Part II, 2012

  Explain what is meant by a substructure of a $\Sigma$-structure $A$, where $\Sigma$ is a first-order signature (possibly including both predicate symbols and function symbols). Show that if $B$ is a substructure of $A$, and $\phi$ is a first-order formula over $\Sigma$ with $n$ free variables, then $[\phi]_{B}=[\phi]_{A} \cap B^{n}$ if $\phi$ is quantifier-free. Show also that $[\phi]_{B} \subseteq[\phi]_{A} \cap B^{n}$ if $\phi$ is an existential formula (that is, one of the form $\left(\exists x_{1}, \ldots, x_{m}\right) \psi$ where $\psi$ is quantifier-free), and $[\phi]_{B} \supseteq[\phi]_{A} \cap B^{n}$ if $\phi$ is a universal formula. Give examples to show that the two latter inclusions can be strict.

  Show also that

  (a) if $T$ is a first-order theory whose axioms are all universal sentences, then any substructure of a $T$-model is a $T$-model;

  (b) if $T$ is a first-order theory such that every first-order formula $\phi$ is $T$-provably equivalent to a universal formula (that is, $T \vdash(\phi \Leftrightarrow \psi)$ for some universal $\psi$ ), and $B$ is a sub-T-model of a $T$-model $A$, then $[\phi]_{B}=[\phi]_{A} \cap B^{n}$ for every first-order formula $\phi$ with $n$ free variables.

  comment

• Paper 4, Section II, H

  Logic and Set Theory

  Part II, 2012

  State and prove Hartogs' lemma. [You may assume the result that any well-ordered set is isomorphic to a unique ordinal.]

  Let $a$ and $b$ be sets such that there is a bijection $a \sqcup b \rightarrow a \times b$. Show, without assuming the Axiom of Choice, that there is either a surjection $b \rightarrow a$ or an injection $b \rightarrow a$. By setting $b=\gamma(a)$ (the Hartogs ordinal of $a$ ) and considering $(a \sqcup b) \times(a \sqcup b)$, show that the assertion 'For all infinite cardinals $m$, we have $m^{2}=m^{\prime}$ implies the Axiom of Choice. [You may assume the Cantor-Bernstein theorem.]

  comment

• Paper 3, Section II, H

  Logic and Set Theory

  Part II, 2012

  Write down either the synthetic or the recursive definitions of ordinal addition and multiplication. Using your definitions, give proofs or counterexamples for the following statements:

  (i) For all $\alpha, \beta$ and $\gamma$, we have $\alpha \cdot(\beta+\gamma)=\alpha \cdot \beta+\alpha \cdot \gamma$.

  (ii) For all $\alpha, \beta$ and $\gamma$, we have $(\alpha+\beta) \cdot \gamma=\alpha \cdot \gamma+\beta \cdot \gamma$.

  (iii) For all $\alpha$ and $\beta$ with $\beta>0$, there exist $\gamma$ and $\delta$ with $\delta<\beta$ and $\alpha=\beta \cdot \gamma+\delta$.

  (iv) For all $\alpha$ and $\beta$ with $\beta>0$, there exist $\gamma$ and $\delta$ with $\delta<\beta$ and $\alpha=\gamma \cdot \beta+\delta$.

  (v) For every $\alpha$, either there exists a cofinal map $f: \omega \rightarrow \alpha$ (that is, one such that $\left.\alpha=\bigcup\left\{f(n)^{+} \mid n \in \omega\right\}\right)$, or there exists $\beta$ such that $\alpha=\omega_{1} \cdot \beta .$

  comment

• Paper 1, Section II, H

  Logic and Set Theory

  Part II, 2012

  State Zorn's lemma, and show how it may be deduced from the Axiom of Choice using the Bourbaki-Witt theorem (which should be clearly stated but not proved).

  Show that, if $a$ and $b$ are distinct elements of a distributive lattice $L$, there is a lattice homomorphism $f: L \rightarrow\{0,1\}$ with $f(a) \neq f(b)$. Indicate briefly how this result may be used to prove the completeness theorem for propositional logic.

  comment

• Paper 2, Section II, G

  Logic and Set Theory

  Part II, 2013

  Explain what is meant by a chain-complete poset. State the Bourbaki-Witt fixedpoint theorem for such posets.

  A poset $P$ is called directed if every finite subset of $P$ (including the empty subset) has an upper bound in $P ; P$ is called directed-complete if every subset of $P$ which is directed (in the induced ordering) has a least upper bound in $P$. Show that the set of all chains in an arbitrary poset $P$, ordered by inclusion, is directed-complete.

  Given a poset $P$, let $[P \rightarrow P]$ denote the set of all order-preserving maps $P \rightarrow P$, ordered pointwise (i.e. $f \leqslant g$ if and only if $f(x) \leqslant g(x)$ for all $x$ ). Show that $[P \rightarrow P]$ is directed-complete if $P$ is.

  Now suppose $P$ is directed-complete, and that $f: P \rightarrow P$ is order-preserving and inflationary. Show that there is a unique smallest set $C \subseteq[P \rightarrow P]$ satisfying

  (a) $f \in C$;

  (b) $C$ is closed under composition (i.e. $g, h \in C \Rightarrow g \circ h \in C$ ); and

  (c) $C$ is closed under joins of directed subsets.

  Show that

  (i) all maps in $C$ are inflationary;

  (ii) $C$ is directed;

  (iii) if $g=\bigvee C$, then all values of $g$ are fixed points of $f$;

  (iv) for every $x \in P$, there exists $y \in P$ with $x \leqslant y=f(y)$.

  comment

• Paper 3, Section II, G

  Logic and Set Theory

  Part II, 2013

  Explain carefully what is meant by syntactic entailment and semantic entailment in the propositional calculus. State the Completeness Theorem for the propositional calculus, and deduce the Compactness Theorem.

  Suppose $P, Q$ and $R$ are pairwise disjoint sets of primitive propositions, and let $\phi \in \mathcal{L}(P \cup Q)$ and $\psi \in \mathcal{L}(Q \cup R)$ be propositional formulae such that $(\phi \Rightarrow \psi)$ is a theorem of the propositional calculus. Consider the set

  $$X=\{\chi \in \mathcal{L}(Q) \mid \phi \vdash \chi\}$$

  Show that $X \cup\{\neg \psi\}$ is inconsistent, and deduce that there exists $\chi \in \mathcal{L}(Q)$ such that both $(\phi \Rightarrow \chi)$ and $(\chi \Rightarrow \psi)$ are theorems. [Hint: assuming $X \cup\{\neg \psi\}$ is consistent, take a suitable valuation $v$ of $Q \cup R$ and show that

  $$\{\phi\} \cup\{q \in Q \mid v(q)=1\} \cup\{\neg q \mid q \in Q, v(q)=0\}$$

  is inconsistent. The Deduction Theorem may be assumed without proof.]

  comment

• Paper 4, Section II, G

  Logic and Set Theory

  Part II, 2013

  State the Axiom of Foundation and the Principle of $\in$-Induction, and show that they are equivalent in the presence of the other axioms of ZF set theory. [You may assume the existence of transitive closures.]

  Given a model $(V, \in)$ for all the axioms of ZF except Foundation, show how to define a transitive class $R$ which, with the restriction of the given relation $\in$, is a model of ZF.

  Given a model $(V, \in)$ of $\mathrm{ZF}$, indicate briefly how one may modify the relation $\in$ so that the resulting structure $\left(V, \in^{\prime}\right)$ fails to satisfy Foundation, but satisfies all the other axioms of $\mathrm{ZF}$. [You need not verify that all the other axioms hold in $\left(V, \in^{\prime}\right)$.]

  comment

• Paper 1, Section II, G

  Logic and Set Theory

  Part II, 2013

  Write down the recursive definitions of ordinal addition, multiplication and exponentiation.

  Given that $F: \mathbf{O n} \rightarrow \mathbf{O n}$ is a strictly increasing function-class (i.e. $\alpha<\beta$ implies $F(\alpha)<F(\beta))$, show that $\alpha \leqslant F(\alpha)$ for all $\alpha$.

  Show that every ordinal $\alpha$ has a unique representation in the form

  $$\alpha=\omega^{\alpha_{1}} \cdot a_{1}+\omega^{\alpha_{2}} \cdot a_{2}+\cdots+\omega^{\alpha_{n}} \cdot a_{n}$$

  where $n \in \omega, \alpha \geqslant \alpha_{1}>\alpha_{2}>\cdots>\alpha_{n}$, and $a_{1}, a_{2}, \ldots, a_{n} \in \omega \backslash\{0\}$.

  Under what conditions can an ordinal $\alpha$ be represented in the form

  $$\omega^{\beta_{1}} \cdot b_{1}+\omega^{\beta_{2}} \cdot b_{2}+\cdots+\omega^{\beta_{m}} \cdot b_{m}$$

  where $\beta_{1}<\beta_{2}<\cdots<\beta_{m}$ and $b_{1}, b_{2}, \ldots, b_{m} \in \omega \backslash\{0\} ?$ Justify your answer.

  [The laws of ordinal arithmetic (associative, distributive, etc.) may be assumed without proof.]

  comment

• Paper 4, Section II, I

  Logic and Set Theory

  Part II, 2014

  Explain what is meant by a chain-complete poset. State the Bourbaki-Witt fixedpoint theorem.

  We call a poset $(P, \leqslant)$ Bourbakian if every order-preserving map $f: P \rightarrow P$ has a least fixed point $\mu(f)$. Suppose $P$ is Bourbakian, and let $f, g: P \rightrightarrows P$ be order-preserving maps with $f(x) \leqslant g(x)$ for all $x \in P$; show that $\mu(f) \leqslant \mu(g)$. [Hint: Consider the function $h: P \rightarrow P$ defined by $h(x)=f(x)$ if $x \leqslant \mu(g), h(x)=\mu(g)$ otherwise.]

  Suppose $P$ is Bourbakian and $f: \alpha \rightarrow P$ is an order-preserving map from an ordinal to $P$. Show that there is an order-preserving map $g: P \rightarrow P$ whose fixed points are exactly the upper bounds of the set $\{f(\beta) \mid \beta<\alpha\}$, and deduce that this set has a least upper bound.

  Let $C$ be a chain with no greatest member. Using the Axiom of Choice and Hartogs' Lemma, show that there is an order-preserving map $f: \alpha \rightarrow C$, for some ordinal $\alpha$, whose image has no upper bound in $C$. Deduce that any Bourbakian poset is chain-complete.

  comment

• Paper 3, Section II, I

  Logic and Set Theory

  Part II, 2014

  Explain what is meant by a structure for a first-order signature $\Sigma$, and describe briefly how first-order terms and formulae in the language over $\Sigma$ are interpreted in a structure. Suppose that $A$ and $B$ are $\Sigma$-structures, and that $\phi$ is a conjunction of atomic formulae over $\Sigma$ : show that an $n$-tuple $\left(\left(a_{1}, b_{1}\right), \ldots,\left(a_{n}, b_{n}\right)\right)$ belongs to the interpretation $\llbracket \phi \rrbracket_{A \times B}$ of $\phi$ in $A \times B$ if and only if $\left(a_{1}, \ldots, a_{n}\right) \in \llbracket \phi \rrbracket_{A}$ and $\left(b_{1}, \ldots, b_{n}\right) \in \llbracket \phi \rrbracket B$.

  A first-order theory $\mathbb{T}$ is called regular if its axioms all have the form

  $$(\forall \vec{x})(\phi \Rightarrow(\exists \vec{y}) \psi),$$

  where $\vec{x}$and $\vec{y}$ are (possibly empty) strings of variables and $\phi$ and $\psi$ are conjunctions of atomic formulae (possibly the empty conjunction $T$ ). Show that if $A$ and $B$ are models of a regular theory $\mathbb{T}$, then so is $A \times B$.

  Now suppose that $\mathbb{T}$ is a regular theory, and that a sentence of the form

  $$(\forall \vec{x})\left(\phi \Rightarrow\left(\psi_{1} \vee \psi_{2} \vee \cdots \vee \psi_{n}\right)\right)$$

  is derivable from the axioms of $\mathbb{T}$, where $\phi$ and the $\psi_{i}$ are conjunctions of atomic formulae. Show that the sentence $(\forall \vec{x})\left(\phi \Rightarrow \psi_{i}\right)$ is derivable for some $i$. [Hint: Suppose not, and use the Completeness Theorem to obtain a suitable family of $\mathbb{T}$-models $A_{1}, \ldots, A_{n}$.]

  comment

• Paper 2, Section II, I

  Logic and Set Theory

  Part II, 2014

  Write down the recursive definitions of ordinal addition, multiplication and exponentiation. Show that, for any nonzero ordinal $\alpha$, there exist unique ordinals $\beta, \gamma$ and $n$ such that $\alpha=\omega^{\beta} . n+\gamma, \gamma<\omega^{\beta}$ and $0<n<\omega$.

  Hence or otherwise show that $\alpha$ (that is, the set of ordinals less than $\alpha$ ) is closed under addition if and only if $\alpha=\omega^{\beta}$ for some $\beta$. Show also that an infinite ordinal $\alpha$ is closed under multiplication if and only if $\alpha=\omega^{\left(\omega^{\gamma}\right)}$ for some $\gamma$.

  [You may assume the standard laws of ordinal arithmetic, and the fact that $\alpha \leqslant \omega^{\alpha}$ for all $\alpha$.]

  comment

• Paper 1, Section II, I

  Logic and Set Theory

  Part II, 2014

  Explain what is meant by saying that a binary relation $r \subseteq a \times a$ is well-founded. Show that $r$ is well-founded if and only if, for any set $b$ and any function $f: \mathcal{P} b \rightarrow b$, there exists a unique function $g: a \rightarrow b$ satisfying

  $$g(x)=f(\{g(y) \mid\langle y, x\rangle \in r\})$$

  for all $x \in a$. [Hint: For 'if', it suffices to take $b=\{0,1\}$, with $f: \mathcal{P} b \rightarrow b$ defined by $\left.f\left(b^{\prime}\right)=1 \Leftrightarrow 1 \in b^{\prime} .\right]$

  comment

• Paper 4, Section II, I

  Logic and Set Theory

  Part II, 2015

  State the Axiom of Foundation and the Principle of $\epsilon$-Induction, and show that they are equivalent (in the presence of the other axioms of $Z F$ ). [You may assume the existence of transitive closures.]

  Explain briefly how the Principle of $\epsilon$-Induction implies that every set is a member of some $V_{\alpha}$.

  Find the ranks of the following sets:

  (i) $\{\omega+1, \omega+2, \omega+3\}$,

  (ii) the Cartesian product $\omega \times \omega$,

  (iii) the set of all functions from $\omega$ to $\omega^{2}$.

  [You may assume standard properties of rank.]

  comment

• Paper 3, Section II, I

  Logic and Set Theory

  Part II, 2015

  (i) State and prove Zorn's Lemma. [You may assume Hartogs' Lemma.] Where in your proof have you made use of the Axiom of Choice?

  (ii) Let $<$ be a partial ordering on a set $X$. Prove carefully that $<$ may be extended to a total ordering of $X$.

  What does it mean to say that $<$ is well-founded?

  If $<$ has an extension that is a well-ordering, must $<$ be well-founded? If $<$ is well-founded, must every total ordering extending it be a well-ordering? Justify your answers.

  comment

• Paper 2, Section II, I

  Logic and Set Theory

  Part II, 2015

  (a) Give the inductive and synthetic definitions of ordinal addition, and prove that they are equivalent. Give the inductive definitions of ordinal multiplication and ordinal exponentiation.

  (b) Answer, with brief justification, the following:

  (i) For ordinals $\alpha, \beta$ and $\gamma$ with $\alpha<\beta$, must we have $\alpha+\gamma<\beta+\gamma$ ? Must we have $\gamma+\alpha<\gamma+\beta$ ?

  (ii) For ordinals $\alpha$ and $\beta$ with $\alpha<\beta$, must we have $\alpha^{\omega}<\beta^{\omega}$ ?

  (iii) Is there an ordinal $\alpha>1$ such that $\alpha^{\omega}=\alpha$ ?

  (iv) Show that $\omega^{\omega_{1}}=\omega_{1}$. Is $\omega_{1}$ the least ordinal $\alpha$ such that $\omega^{\alpha}=\alpha$ ?

  [You may use standard facts about ordinal arithmetic.]

  comment

• Paper 1, Section II, I

  Logic and Set Theory

  Part II, 2015

  State and prove the Completeness Theorem for Propositional Logic.

  [You do not need to give definitions of the various terms involved. You may assume the Deduction Theorem, provided that you state it precisely.]

  State the Compactness Theorem and the Decidability Theorem, and deduce them from the Completeness Theorem.

  Let $S$ consist of the propositions $p_{n+1} \Rightarrow p_{n}$ for $n=1,2,3, \ldots$. Does $S$ prove $p_{1}$ ? Justify your answer. [Here $p_{1}, p_{2}, p_{3}, \ldots$ are primitive propositions.]

  comment

• Paper 2, Section II, F

  Logic and Set Theory

  Part II, 2016

  Define the von Neumann hierarchy of sets $V_{\alpha}$, and show that each $V_{\alpha}$ is a transitive set. Explain what is meant by saying that a binary relation on a set is well-founded and extensional. State Mostowski's Theorem.

  Let $r$ be the binary relation on $\omega$ defined by: $\langle m, n\rangle \in r$ if and only if $2^{m}$ appears in the base-2 expansion of $n$ (i.e., the unique expression for $n$ as a sum of distinct powers of 2 ). Show that $r$ is well-founded and extensional. To which transitive set is $(\omega, r)$ isomorphic? Justify your answer.

  comment

• Paper 3, Section II, F

  Logic and Set Theory

  Part II, 2016

  State the Completeness Theorem for the first-order predicate calculus, and deduce the Compactness Theorem.

  Let $\mathbb{T}$ be a first-order theory over a signature $\Sigma$ whose axioms all have the form $(\forall \vec{x}) \phi$ where $\vec{x}$is a (possibly empty) string of variables and $\phi$ is quantifier-free. Show that every substructure of a $\mathbb{T}$-model is a $\mathbb{T}$-model, and deduce that if $\mathbb{T}$ is consistent then it has a model in which every element is the interpretation of a closed term of $\mathcal{L}(\Sigma)$. $[$ You may assume the result that if $B$ is a substructure of $A$ and $\phi$ is a quantifier-free formula with $n$ free variables, then $\llbracket \phi \rrbracket_{B}=\llbracket \phi \rrbracket_{A} \cap B^{n}$.]

  Now suppose $\mathbb{T} \vdash(\exists x) \psi$ where $\psi$ is a quantifier-free formula with one free variable $x$. Show that there is a finite list $\left(t_{1}, t_{2}, \ldots, t_{n}\right)$ of closed terms of $\mathcal{L}(\Sigma)$ such that

  $$\mathbb{T} \vdash\left(\psi\left[t_{1} / x\right] \vee \psi\left[t_{2} / x\right] \vee \cdots \vee \psi\left[t_{n} / x\right]\right)$$

  comment

• Paper 1, Section II, F

  Logic and Set Theory

  Part II, 2016

  Which of the following statements are true? Justify your answers. (a) Every ordinal is of the form $\alpha+n$, where $\alpha$ is a limit ordinal and $n \in \omega$. (b) Every ordinal is of the form $\omega^{\alpha} \cdot m+n$, where $\alpha$ is an ordinal and $m, n \in \omega$. (c) If $\alpha=\omega \cdot \alpha$, then $\alpha=\omega^{\omega} \cdot \beta$ for some $\beta$. (d) If $\alpha=\omega^{\alpha}$, then $\alpha$ is uncountable. (e) If $\alpha>1$ and $\alpha=\alpha^{\omega}$, then $\alpha$ is uncountable.

  [Standard laws of ordinal arithmetic may be assumed, but if you use the Division Algorithm you should prove it.]

  comment

• Paper 4, Section II, F

  Logic and Set Theory

  Part II, 2016

  (a) State Zorn's Lemma, and use it to prove that every nontrivial distributive lattice $L$ admits a lattice homomorphism $L \rightarrow\{0,1\}$.

  (b) Let $S$ be a propositional theory in a given language $\mathcal{L}$. Sketch the way in which the equivalence classes of formulae of $\mathcal{L}$, modulo $S$-provable equivalence, may be made into a Boolean algebra. [Detailed proofs are not required, but you should define the equivalence relation explicitly.]

  (c) Hence show how the Completeness Theorem for propositional logic may be deduced from the result of part (a).

  comment

• Paper 3, Section II, H

  Logic and Set Theory

  Part II, 2017

  State and prove Zorn's Lemma. [You may assume Hartogs' Lemma.] Indicate clearly where in your proof you have made use of the Axiom of Choice.

  Show that $\mathbb{R}$ has a basis as a vector space over $\mathbb{Q}$.

  Let $V$ be a vector space over $\mathbb{Q}$. Show that all bases of $V$ have the same cardinality.

  [Hint: How does the cardinality of $V$ relate to the cardinality of a given basis?]

  comment

• Paper 2, Section II, H

  Logic and Set Theory

  Part II, 2017

  Give the inductive and synthetic definitions of ordinal addition, and prove that they are equivalent.

  Which of the following are always true for ordinals $\alpha, \beta$ and $\gamma$ and which can be false? Give proofs or counterexamples as appropriate.

  (i) $\alpha+\beta=\beta+\alpha$

  (ii) $(\alpha+\beta) \gamma=\alpha \gamma+\beta \gamma$

  (iii) $\alpha(\beta+\gamma)=\alpha \beta+\alpha \gamma$

  (iv) If $\alpha \beta=\beta \alpha$ then $\alpha^{2} \beta^{2}=\beta^{2} \alpha^{2}$

  (v) If $\alpha^{2} \beta^{2}=\beta^{2} \alpha^{2}$ then $\alpha \beta=\beta \alpha$

  [In parts (iv) and (v) you may assume without proof that ordinal multiplication is associative.]

  comment

• Paper 4, Section II, H

  Logic and Set Theory

  Part II, 2017

  Prove that every set has a transitive closure. [If you apply the Axiom of Replacement to a function-class $F$, you must explain clearly why $F$ is indeed a function-class.]

  State the Axiom of Foundation and the Principle of $\epsilon$-Induction, and show that they are equivalent (in the presence of the other axioms of $\mathrm{ZFC}$ ).

  State the $\epsilon$-Recursion Theorem.

  Sets $C_{\alpha}$ are defined for each ordinal $\alpha$ by recursion, as follows: $C_{0}=\emptyset, C_{\alpha+1}$ is the set of all countable subsets of $C_{\alpha}$, and $C_{\lambda}=\cup_{\alpha<\lambda} C_{\alpha}$ for $\lambda$ a non-zero limit. Does there exist an $\alpha$ with $C_{\alpha+1}=C_{\alpha}$ ? Justify your answer.

  comment

• Paper 1, Section II, H

  Logic and Set Theory

  Part II, 2017

  State the Completeness Theorem for Propositional Logic.

  [You do not need to give definitions of the various terms involved.]

  State the Compactness Theorem and the Decidability Theorem, and deduce them from the Completeness Theorem.

  A set $S$ of propositions is called finitary if there exists a finite set $T$ of propositions such that $\{t: S \vdash t\}=\{t: T \vdash t\}$. Give examples to show that an infinite set of propositions may or may not be finitary.

  Now let $A$ and $B$ be sets of propositions such that every valuation is a model of exactly one of $A$ and $B$. Show that there exist finite subsets $A^{\prime}$ of $A$ and $B^{\prime}$ of $B$ with $A^{\prime} \cup B^{\prime} \models \perp$, and deduce that $A$ and $B$ are finitary.

  comment

• Paper 4, Section II, G

  Logic and Set Theory

  Part II, 2018

  State and prove the $\epsilon$-Recursion Theorem. [You may assume the Principle of $\epsilon-$ Induction.]

  What does it mean to say that a relation $r$ on a set $x$ is well-founded and extensional? State and prove Mostowski's Collapsing Theorem. [You may use any recursion theorem from the course, provided you state it precisely.]

  For which sets $x$ is it the case that every well-founded extensional relation on $x$ is isomorphic to the relation $\epsilon$ on some transitive subset of $V_{\omega}$ ?

  comment

• Paper 3, Section II, G

  Logic and Set Theory

  Part II, 2018

  State and prove the Compactness Theorem for first-order predicate logic. State and prove the Upward Löwenheim-Skolem Theorem.

  [You may assume the Completeness Theorem for first-order predicate logic.]

  For each of the following theories, either give axioms (in the specified language) for the theory or prove that the theory is not axiomatisable.

  (i) The theory of finite groups (in the language of groups).

  (ii) The theory of groups in which every non-identity element has infinite order (in the language of groups).

  (iii) The theory of total orders (in the language of posets).

  (iv) The theory of well-orderings (in the language of posets).

  If a theory is axiomatisable by a set $S$ of sentences, and also by a finite set $T$ of sentences, does it follow that the theory is axiomatisable by some finite subset of $S$ ? Justify your answer.

  comment

• Paper 2, Section II, G

  Logic and Set Theory

  Part II, 2018

  State and prove the Knaster-Tarski Fixed-Point Theorem. Deduce the SchröderBernstein Theorem.

  Show that the poset $P$ of all countable subsets of $\mathbb{R}$ (ordered by inclusion) is not complete.

  Find an order-preserving function $f: P \rightarrow P$ that does not have a fixed point. [Hint: Start by well-ordering the reals.]

  comment

• Paper 1, Section II, G

  Logic and Set Theory

  Part II, 2018

  Give the inductive definition of ordinal exponentiation. Use it to show that $\alpha^{\beta} \leqslant \alpha^{\gamma}$ whenever $\beta \leqslant \gamma$ (for $\alpha \geqslant 1$ ), and also that $\alpha^{\beta}<\alpha^{\gamma}$ whenever $\beta<\gamma($ for $\alpha \geqslant 2)$.

  Give an example of ordinals $\alpha$ and $\beta$ with $\omega<\alpha<\beta$ such that $\alpha^{\omega}=\beta^{\omega}$.

  Show that $\alpha^{\beta+\gamma}=\alpha^{\beta} \alpha^{\gamma}$, for any ordinals $\alpha, \beta, \gamma$, and give an example to show that we need not have $(\alpha \beta)^{\gamma}=\alpha^{\gamma} \beta^{\gamma}$.

  For which ordinals $\alpha$ do we have $\alpha^{\omega_{1}} \geqslant \omega_{1}$ ? And for which do we have $\alpha^{\omega_{1}} \geqslant \omega_{2}$ ? Justify your answers.

  [You may assume any standard results not concerning ordinal exponentiation.]

  comment

• Paper 4, Section II, I

  Logic and Set Theory

  Part II, 2019

  Define the cardinals $\aleph_{\alpha}$, and explain briefly why every infinite set has cardinality $\operatorname{an} \aleph_{\alpha} .$

  Show that if $\kappa$ is an infinite cardinal then $\kappa^{2}=\kappa$.

  Let $X_{1}, X_{2}, \ldots, X_{n}$ be infinite sets. Show that $X_{1} \cup X_{2} \cup \cdots \cup X_{n}$ must have the same cardinality as $X_{i}$ for some $i$.

  Let $X_{1}, X_{2}, \ldots$ be infinite sets, no two of the same cardinality. Is it possible that $X_{1} \cup X_{2} \cup \ldots$ has the same cardinality as some $X_{i}$ ? Justify your answer.

  comment

• Paper 3, Section II, I

  Logic and Set Theory

  Part II, 2019

  Define the von Neumann hierarchy of sets $V_{\alpha}$. Show that each $V_{\alpha}$ is transitive, and explain why $V_{\alpha} \subset V_{\beta}$ whenever $\alpha \leqslant \beta$. Prove that every set $x$ is a member of some $V_{\alpha}$.

  Which of the following are true and which are false? Give proofs or counterexamples as appropriate. [You may assume standard properties of rank.]

  (i) If the rank of a set $x$ is a (non-zero) limit then $x$ is infinite.

  (ii) If the rank of a set $x$ is countable then $x$ is countable.

  (iii) If every finite subset of a set $x$ has rank at most $\alpha$ then $x$ has rank at most $\alpha$.

  (iv) For every ordinal $\alpha$ there exists a set of $\operatorname{rank} \alpha$.

  comment

• Paper 2, Section II, I

  Logic and Set Theory

  Part II, 2019

  Give the inductive and synthetic definitions of ordinal addition, and prove that they are equivalent.

  Which of the following assertions about ordinals $\alpha, \beta$ and $\gamma$ are always true, and which can be false? Give proofs or counterexamples as appropriate.

  (i) $\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma$.

  (ii) If $\alpha$ and $\beta$ are uncountable then $\alpha+\beta=\beta+\alpha$.

  (iii) $\alpha(\beta \gamma)=(\alpha \beta) \gamma$.

  (iv) If $\alpha$ and $\beta$ are infinite and $\alpha+\beta=\beta+\alpha$ then $\alpha \beta=\beta \alpha$.

  comment

• Paper 1, Section II, I

  Logic and Set Theory

  Part II, 2019

  State the completeness theorem for propositional logic. Explain briefly how the proof of this theorem changes from the usual proof in the case when the set of primitive propositions may be uncountable.

  State the compactness theorem and the decidability theorem, and deduce them from the completeness theorem.

  A poset $(X,<)$ is called two-dimensional if there exist total orders $<_{1}$ and $<_{2}$ on $X$ such that $x<y$ if and only if $x<_{1} y$ and $x<_{2} y$. By applying the compactness theorem for propositional logic, show that if every finite subset of a poset is two-dimensional then so is the poset itself.

  [Hint: Take primitive propositions $p_{x, y}$ and $q_{x, y}$, for each distinct $x, y \in X$, with the intended interpretation that $p_{x, y}$ is true if and only if $x<_{1} y$ and $q_{x, y}$ is true if and only if $x<2 y .]$

  comment

• Paper 1, Section II, H

  Logic and Set Theory

  Part II, 2020

  [Throughout this question, assume the axiom of choice.]

  Let $\kappa, \lambda$ and $\mu$ be cardinals. Define $\kappa+\lambda, \kappa \lambda$ and $\kappa^{\lambda}$. What does it mean to say $\kappa \leqslant \lambda$ ? Show that $\left(\kappa^{\lambda}\right)^{\mu}=\kappa^{\lambda \mu}$. Show also that $2^{\kappa}>\kappa$.

  Assume now that $\kappa$ and $\lambda$ are infinite. Show that $\kappa \kappa=\kappa$. Deduce that $\kappa+\lambda=\kappa \lambda=\max \{\kappa, \lambda\}$. Which of the following are always true and which can be false? Give proofs or counterexamples as appropriate. (i) $\kappa^{\lambda}=2^{\lambda}$; (ii) $\kappa \leqslant \lambda \Longrightarrow \kappa^{\lambda}=2^{\lambda}$; (iii) $\kappa^{\lambda}=\lambda^{\kappa}$.

  comment

• Paper 2, Section II, H

  Logic and Set Theory

  Part II, 2020

  (a) This part of the question is concerned with propositional logic.

  Let $P$ be a set of primitive propositions. Let $S \subset L(P)$ be a consistent, deductively closed set such that for every $t \in L(P)$ either $t \in S$ or $\neg t \in S$. Show that $S$ has a model.

  (b) This part of the question is concerned with predicate logic.

  (i) State Gödel's completeness theorem for first-order logic. Deduce the compactness theorem, which you should state precisely.

  (ii) Let $X$ be an infinite set. For each $x \in X$, let $L_{x}$ be a subset of $X$. Suppose that for any finite $Y \subseteq X$ there exists a function $f_{Y}: Y \rightarrow\{1, \ldots, 100\}$ such that for all $x \in Y$ and all $y \in Y \cap L_{x}, f_{Y}(x) \neq f_{Y}(y)$. Show that there exists a function $F: X \rightarrow\{1, \ldots, 100\}$ such that for all $x \in X$ and all $y \in L_{x}, F(x) \neq F(y)$.

  comment

• Paper 3, Section II, $16 \mathrm{H}$

  Logic and Set Theory

  Part II, 2020

  Let $(V, \in)$ be a model of ZF. Give the definition of a class and a function class in $V$. Use the concept of function class to give a short, informal statement of the Axiom of Replacement.

  Let $z_{0}=\omega$ and, for each $n \in \omega$, let $z_{n+1}=\mathcal{P} z_{n}$. Show that $y=\left\{z_{n} \mid n \in \omega\right\}$ is a set.

  We say that a set $x$ is small if there is an injection from $x$ to $z_{n}$ for some $n \in \omega$. Let HS be the class of sets $x$ such that every member of $\mathrm{TC}(\{x\})$ is small, where $\mathrm{TC}(\{x\})$ is the transitive closure of $\{x\}$. Show that $n \in \mathbf{H S}$ for all $n \in \omega$ and deduce that $\omega \in \mathbf{H S}$. Show further that $z_{n} \in \mathbf{H S}$ for all $n \in \omega$. Deduce that $y \in \mathbf{H S}$.

  Is $(\mathbf{H S}, \in)$ a model of ZF? Justify your answer.

  $[$ Recall that $0=\emptyset$ and that $n+1=n \cup\{n\}$ for all $n \in \omega .]$

  comment

• Paper 4, Section II, 16H

  Logic and Set Theory

  Part II, 2020

  (a) State Zorn's lemma.

  [Throughout the remainder of this question, assume Zorn's lemma.]

  (b) Let $P$ be a poset in which every non-empty chain has an upper bound and let $x \in P$. By considering the poset $P_{x}=\{y \in P \mid x \leqslant y\}$, show that $P$ has a maximal element $\sigma$ with $x \leqslant \sigma$.

  (c) A filter is a non-empty subset $\mathcal{F} \subset \mathcal{P}(\mathbb{N})$ satisfying the following three conditions:

  • if $A, B \in \mathcal{F}$ then $A \cap B \in \mathcal{F}$

  • if $A \in \mathcal{F}$ and $A \subset B$ then $B \in \mathcal{F}$

  • $\emptyset \notin \mathcal{F} .$

  An ultrafilter is a filter $\mathcal{U}$ such that for all $A \subset \mathbb{N}$ we have either $A \in \mathcal{U}$ or $A^{c} \in \mathcal{U}$, where $A^{c}=\mathbb{N} \backslash A$.

  (i) For each $n \in \mathbb{N}$, show that $\mathcal{U}_{n}=\{A \subset \mathbb{N} \mid n \in A\}$ is an ultrafilter.

  (ii) Show that $\mathcal{F}=\left\{A \subset \mathbb{N} \mid A^{c}\right.$ is finite $\}$ is a filter but not an ultrafilter, and that for all $n \in \mathbb{N}$ we have $\mathcal{F} \not \subset \mathcal{U}_{n}$.

  (iii) Does there exist an ultrafilter $\mathcal{U}$ such that $\mathcal{U} \neq \mathcal{U}_{n}$ for any $n \in \mathbb{N}$ ? Justify your answer.

  comment

• Paper 1, Section II, 16G

  Logic and Set Theory

  Part II, 2021

  Let $S$ and $T$ be sets of propositional formulae.

  (a) What does it mean to say that $S$ is deductively closed? What does it mean to say that $S$ is consistent? Explain briefly why if $S$ is inconsistent then some finite subset of $S$ is inconsistent.

  (b) We write $S \vdash T$ to mean $S \vdash t$ for all $t \in T$. If $S \vdash T$ and $T \vdash S$ we say $S$ and $T$ are equivalent. If $S$ is equivalent to a finite set $F$ of formulae we say that $S$ is finitary. Show that if $S$ is finitary then there is a finite set $R \subset S$ with $R \vdash S$.

  (c) Now let $T_{0}, T_{1}, T_{2}, \ldots$ be deductively closed sets of formulae with

  $$T_{0} \subset T_{1} \subset T_{2} \subset \cdots$$

  Show that each $T_{i}$ is consistent.

  Let $T=\bigcup_{i=0}^{\infty} T_{i}$. Show that $T$ is consistent and deductively closed, but that it is not finitary.

  comment

• Paper 2, Section II, G

  Logic and Set Theory

  Part II, 2021

  Write down the inductive definition of ordinal exponentiation. Show that $\omega^{\alpha} \geqslant \alpha$ for every ordinal $\alpha$. Deduce that, for every ordinal $\alpha$, there is a least ordinal $\alpha^{*}$ with $\omega^{\alpha^{*}}>\alpha$. Show that, if $\alpha \neq 0$, then $\alpha^{*}$ must be a successor ordinal.

  Now let $\alpha$ be a non-zero ordinal. Show that there exist ordinals $\beta$ and $\gamma$, where $\gamma<\alpha$, and a positive integer $n$ such that $\alpha=\omega^{\beta} n+\gamma$. Hence, or otherwise, show that $\alpha$ can be written in the form

  $$\alpha=\omega^{\beta_{1}} n_{1}+\omega^{\beta_{2}} n_{2}+\cdots+\omega^{\beta_{k}} n_{k}$$

  where $k, n_{1}, n_{2}, \ldots, n_{k}$ are positive integers and $\beta_{1}>\beta_{2}>\cdots>\beta_{k}$ are ordinals. [We call this the Cantor normal form of $\alpha$, and you may henceforth assume that it is unique.]

  Given ordinals $\delta_{1}, \delta_{2}$ and positive integers $m_{1}, m_{2}$ find the Cantor normal form of $\omega^{\delta_{1}} m_{1}+\omega^{\delta_{2}} m_{2}$. Hence, or otherwise, given non-zero ordinals $\alpha$ and $\alpha^{\prime}$, find the Cantor normal form of $\alpha+\alpha^{\prime}$ in terms of the Cantor normal forms

  $$\alpha=\omega^{\beta_{1}} n_{1}+\omega^{\beta_{2}} n_{2}+\cdots+\omega^{\beta_{k}} n_{k}$$

  and

  $$\alpha^{\prime}=\omega^{\beta_{1}^{\prime}} n_{1}^{\prime}+\omega^{\beta_{2}^{\prime}} n_{2}^{\prime}+\cdots+\omega^{\beta_{k^{\prime}}^{\prime}} n_{k^{\prime}}^{\prime}$$

  of $\alpha$ and $\alpha^{\prime}$.

  comment

• Paper 3, Section II, 16G

  Logic and Set Theory

  Part II, 2021

  (a) Let $\kappa$ and $\lambda$ be cardinals. What does it mean to say that $\kappa<\lambda$ ? Explain briefly why, assuming the Axiom of Choice, every infinite cardinal is of the form $\aleph_{\alpha}$ for some ordinal $\alpha$, and that for every ordinal $\alpha$ we have $\aleph_{\alpha+1}<2^{2^{\aleph_{\alpha}}}$.

  (b) Henceforth, you should not assume the Axiom of Choice.

  Show that, for any set $x$, there is an injection from $x$ to its power set $\mathcal{P} x$, but there is no bijection from $x$ to $\mathcal{P} x$. Deduce that if $\kappa$ is a cardinal then $\kappa<2^{\kappa}$.

  Let $x$ and $y$ be sets, and suppose that there exists a surjection $f: x \rightarrow y$. Show that there exists an injection $g: \mathcal{P} y \rightarrow \mathcal{P} x$.

  Let $\alpha$ be an ordinal. Prove that $\aleph_{\alpha} \aleph_{\alpha}=\aleph_{\alpha}$.

  By considering $\mathcal{P}\left(\omega_{\alpha} \times \omega_{\alpha}\right)$ as the set of relations on $\omega_{\alpha}$, or otherwise, show that there exists a surjection $f: \mathcal{P}\left(\omega_{\alpha} \times \omega_{\alpha}\right) \rightarrow \omega_{\alpha+1}$. Deduce that $\aleph_{\alpha+1}<2^{2^{\kappa_{\alpha}}}$.

  comment

• Paper 4, Section II, 16G

  Logic and Set Theory

  Part II, 2021

  Write down the Axiom of Foundation.

  What is the transitive closure of a set $x$ ? Prove carefully that every set $x$ has a transitive closure. State and prove the principle of $\in$-induction.

  Let $(V, \in)$ be a model of $\mathrm{ZF}$. Let $F: V \rightarrow V$ be a surjective function class such that for all $x, y \in V$ we have $F(x) \in F(y)$ if and only if $x \in y$. Show, by $\in$-induction or otherwise, that $F$ is the identity.

  comment